package 剑指offer;

public class p11输出旋转数组的最小元素 {

    public int minArray(int[] numbers) {
        //本题使用 二分法
        //二分法：针对有序数组进行分割
        int left=numbers[0];
        int right=numbers.length-1;

        while (left<right) {
            //当 left==right，即左右指针相遇时，结束循环

            int mid=(left+right)/2;//遵守向下取整
            if (numbers[mid]>numbers[right]) {
                //证明 最小元素在 [mid+1 , right]之间
                left=mid+1;

            }else if (numbers[mid] < numbers[right]) {
                //证明 最小元素在 [left , mid]之间，第一个[可开可闭，不确定
                right=mid;
            }else {
                //当 numbers[mid] == numbers[right] 时，将 right--
                right--;
            }
        }
        return numbers[left];
    }


    public int minArray1(int[] numbers) {
        int i=0;
        int j=numbers.length-1;

        while (i<j) {
            int m=(i+j)/2;
            if (numbers[m]>numbers[j]) {
                //m还在左排序数组中
                i=m+1;
            }else if (numbers[m]<numbers[j]){
                //m在右排序数组中
                j=m;
            }else{
                //numbers[m] == numbers[j]
                j--;
            }
        }
        return numbers[i];

    }
}
